package org.mycollections;

import java.util.Comparator;

class MyCollectionUtils {

    private MyCollectionUtils() {
    }

    static void swap(Object[] arr, int i, int j) {

        Object temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static int partition(Object[] arr, int left, int right) {

        int i = left, j = right;
        Object pivot = arr[(left + right) >>> 1];

        while (i <= j) {

            while (((Comparable) arr[i]).compareTo(pivot) < 0) {
                i++;
            }
            while (((Comparable) arr[j]).compareTo(pivot) > 0) {
                j--;
            }

            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }

        return i;
    }

    private static int partition(Object[] arr, int left, int right, Comparator c) {

        int i = left, j = right;
        Object pivot = arr[(left + right) >>> 1];

        while (i <= j) {

            while (c.compare(arr[i], pivot) < 0) {
                i++;
            }
            while (c.compare(arr[j], pivot) > 0) {
                j--;
            }

            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }

        return i;
    }

    static void quickSort(Object[] arr, int left, int right, Comparator c) {

        int index;

        if (c == null) {
            index = partition(arr, left, right);
        } else {
            index = partition(arr, left, right, c);
        }

        if (left < index - 1) {
            quickSort(arr, left, index - 1, c);
        }
        if (index < right) {
            quickSort(arr, index, right, c);
        }
    }

    static void bubbleSort(Object[] arr, Comparator c) {

        int j;
        boolean flag = true;
        while (flag) {

            flag = false;
            for (j = 0; j < arr.length - 1; j++) {

                int compareResult;
                if (c == null) {
                    compareResult = ((Comparable) arr[j]).compareTo(arr[j + 1]);
                } else {
                    compareResult = c.compare(arr[j], arr[j + 1]);
                }

                if (compareResult > 0) {
                    swap(arr, j, j + 1);
                    flag = true;
                }
            }
        }
    }

    static boolean isSorted(Object[] arr) {

        for (int i = 1; i < arr.length; i++) {
            if (((Comparable) arr[i]).compareTo(arr[i - 1]) < 0) {
                return false;
            }
        }
        return true;
    }

}
